package g

/*
 * @lc app=leetcode.cn id=22 lang=golang
 *
 * [22] 小括号生成
 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 1 <= n <= 8

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
*/

// @lc code=start

// 参考 https://leetcode.cn/problems/generate-parentheses/solution/zui-jian-dan-yi-dong-de-dong-tai-gui-hua-bu-lun-da/
func generateParenthesis(n int) []string {
	if n == 0 {
		return nil
	}
	// 计算所有的情况，动态规划，n依赖0~n-1的结果
	var results [][]string
	results = append(results, []string{""})   // 0组括号时记为""
	results = append(results, []string{"()"}) // 1组括号只有一种情况
	for i := 2; i <= n; i++ {                 // 开始计算i组括号时的括号组合
		// 第i组比第i-1多一对括号，第i-1组和一对括号所有的有效组合，就是第i组的情况
		// 反过来一样，一对括号和第i-1组的有效组合，就是第i组的情况
		// 固定一对括号，剩下的插入其中，一部分在这个括号内部，一部分在括号外部(右边)
		// "(" + 【i=p时所有括号的排列组合】 + ")" + 【i=q时所有括号的排列组合】
		var result []string
		for j := 0; j < i; j++ { // 开始遍历 p q ，其中p+q=i-1 , j 作为索引
			resultLeft := results[j]      // p = j 时的括号组合情况
			resultRight := results[i-1-j] // q = (i-1) - j 时的括号组合情况
			for _, k1 := range resultLeft {
				for _, k2 := range resultRight {
					el := "(" + k1 + ")" + k2
					result = append(result, el) // 把所有可能的情况添加到 l 中
				}
			}
		}
		results = append(results, result) // l这个list就是i组括号的所有情况，添加到total_l中，继续求解i=i+1的情况
	}
	return results[n]
}

// @lc code=end
